# 最小权值(好题)
# 此类问题常见于 最优二叉树构造 或 递归结构的最优化问题，例如：
# - 通信网络中的最优编码树
# - 编译器中的表达式树优化
# - 动态规划中的分治代价模型
# 通过动态规划高效计算每个子树的最优解，避免重复计算，是处理树形递归问题的经典方法。
import sys

sys.setrecursionlimit(10000)


def min_weight_complete(n):
    # 假设有n个节点组成的完全2叉树
    tree = [[] for _ in range(n + 1)]
    tree[0] = [1]
    for i in range(2, n + 1):
        tree[i // 2].append(i)

    def dfs(curr):
        if not tree[curr]:
            return 1, 1  # W(curr), C(curr)

        wl = cl = wr = cr = 0
        for i in range(len(tree[curr])):
            if i == 0:
                wl, cl = dfs(tree[curr][i])
            if i == 1:
                wr, cr = dfs(tree[curr][i])

        return 1 + 2 * wl + 3 * wr + (cl ** 2) * cr, cl + cr + 1

    return dfs(1)


def min_weight_l_line(n):
    # 退化成一条直线的树, 全部节点只有左子节点
    tree = [[] for _ in range(n + 1)]
    tree[0] = [1]
    for i in range(2, n + 1):
        tree[i - 1].append(i)

    def dfs(curr):
        if not tree[curr]:
            return 1, 1  # W(curr), C(curr)

        wl = cl = wr = cr = 0
        wl, cl = dfs(tree[curr][0])

        return 1 + 2 * wl + 3 * wr + (cl ** 2) * cr, cl + cr + 1

    return dfs(1)


def min_weight_r_line(n):
    # 退化成一条直线的树, 全部节点只有右子节点
    tree = [[] for _ in range(n + 1)]
    tree[0] = [1]
    for i in range(2, n + 1):
        tree[i - 1].append(i)

    def dfs(curr):
        if not tree[curr]:
            return 1, 1  # W(curr), C(curr)

        wl = cl = wr = cr = 0
        wr, cr = dfs(tree[curr][0])

        return 1 + 2 * wl + 3 * wr + (cl ** 2) * cr, cl + cr + 1

    return dfs(1)


def min_weight_dp(n):
    dp = [float('inf') for _ in range(n + 1)]
    dp[0], dp[1] = 0, 1  # dp[i] 表示总计i个节点时的最小权值
    for i in range(2, n + 1):
        for left in range(i):  # 设有left个左子节点
            right = i - 1 - left  # 右子树节点数 = 总节点数-根节点-左子树
            dp[i] = min(dp[i], 1 + 2 * dp[left] + 3 * dp[right] + left * left * right)
    return dp[-1]


if __name__ == '__main__':
    print(min_weight_complete(2021))
    # print(min_weight_l_line(2021))
    # print(min_weight_r_line(2021))
    print(min_weight_dp(2021))
